package com.sheng.leetcode.year2022.month04.day02;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/04/02
 *
 * 420. 强密码检验器
 *
 * 如果一个密码满足下述所有条件，则认为这个密码是强密码：
 * 由至少 6 个，至多 20 个字符组成。
 * 至少包含 一个小写 字母，一个大写 字母，和 一个数字 。
 * 同一字符 不能 连续出现三次 (比如 "...aaa..." 是不允许的, 但是 "...aa...a..." 如果满足其他条件也可以算是强密码)。
 * 给你一个字符串 password ，返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0 。
 *
 * 在一步修改操作中，你可以：
 *
 * 插入一个字符到 password ，
 * 从 password 中删除一个字符，或
 * 用另一个字符来替换 password 中的某个字符。
 *
 * 示例 1：
 *
 * 输入：password = "a"
 * 输出：5
 * 示例 2：
 *
 * 输入：password = "aA1"
 * 输出：3
 * 示例 3：
 *
 * 输入：password = "1337C0d3"
 * 输出：0
 *
 * 提示：
 *
 * 1 <= password.length <= 50
 * password 由字母、数字、点 '.' 或者感叹号 '!'
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/strong-password-checker
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0420 {

    @Test
    public void test01(){
        String password = "aaaa";
        System.out.println(new Solution().strongPasswordChecker(password));
    }
}
class Solution {
    public int strongPasswordChecker(String password) {
        char[] cs = password.toCharArray();
        int n = password.length();
        int A = 0, B = 0, C = 0;
        for (char c : cs) {
             if (c >= 'a' && c <= 'z') {
                 A = 1;
             } else if (c >= '0' && c <= '9') {
                 B = 1;
             } else if (c >= 'A' && c <= 'Z') {
                 C = 1;
             }
        }
        //该字符串是否具有小写大写和数字
        int m = A + B + C;
        if (n < 6) {
            //长度小于6
            return Math.max(6 - n, 3 - m);
        } else if(n >= 6 && n <= 20) {
            //长度大于等于6，小于等于20，只需要替换
            //tot代表连续长度不低于3的长度的个数
            int tot = 0;
            //死循环，求出字符串中tot的长度
            for (int i = 0; i < n; ) {
                int j = i;
                //如果i和j对应位置的字符相同，则j++，j的代表字符串中从i开始某一段相同数量字符的末尾
                while (j < n && cs[j] == cs[i]) {
                    j++;
                }
                //cnt代表字符串中某一段相同字符的长度
                int cnt = j - i;
                //相同字符长度大于等于3
                if (cnt >= 3) {
                    //tot = tot + cnt / 3
                    tot += cnt / 3;
                }
                //相同一段字符走过后将j的坐标赋值给i
                i = j;
            }
            //将连续长度不低于3的长度替换的次数
            return Math.max(tot, 3 - m);
        } else {
            //长度超过20
            int tot = 0;
            /**
             * 新建一个长度为3的数组cnts
             * 0：长度刚好为3的倍数连续字符串的数量
             * 1：长度为1的字符串的数量
             * 2：长度为2的字符串的数量
             */
            int[] cnts = new int[3];
            //死循环，求出字符串中tot的长度
            for (int i = 0; i < n; ) {
                int j = i;
                while (j < n && cs[j] == cs[i]) {
                    j++;
                }
                int cnt = j - i;
                if (cnt >= 3) {
                    tot += cnt / 3;
                    //与之前不同新增的一行，作用是将cnts中长度不同的字符串的数量+1
                    cnts[cnt % 3]++;
                }
                i = j;
            }
            /**
             * base：字符串超出20的长度数，这一段是一定要操作的，要减去
             * cur：值和base相等，作用是
             */
            int base = n - 20, cur = base;
            //循环3次
            for (int i = 0; i < 3; i++) {
                //如果i等于2，将cnts数组最后一个数赋值为tot，即赋值为连续长度不低于3的长度的个数
                if (i == 2) {
                    cnts[i] = tot;
                }
                //如果cnts数组中的某一位不等于0，同时，字符串长度大于20
                if (cnts[i] != 0 && cur != 0) {
                    //求cnts[i] * (i + 1)和cur中小的一个数，并赋值给t
                    int t = Math.min(cnts[i] * (i + 1), cur);
                    //cur = cur - t
                    cur -= t;
                    //tot = tot - t / (i + 1)
                    tot -= t / (i + 1);
                }
            }
            //长度超过20的数量加上
            return base + Math.max(tot, 3 - m);
        }
    }
}


/**
 * class Solution {
 *     public int strongPasswordChecker(String password) {
 *         char[] cs = password.toCharArray();
 *         int n = cs.length;
 *         int A = 0, B = 0, C = 0;
 *         for (char c : cs) {
 *             if (c >= 'a' && c <= 'z') A = 1;
 *             else if (c >= '0' && c <= '9') B = 1;
 *             else if (c >= 'A' && c <= 'Z') C = 1;
 *         }
 *         int m = A + B + C;
 *         if (n < 6) {
 *             return Math.max(6 - n, 3 - m);
 *         } else if (n <= 20) {
 *             int tot = 0;
 *             for (int i = 0; i < n; ) {
 *                 int j = i;
 *                 while (j < n && cs[j] == cs[i]) j++;
 *                 int cnt = j - i;
 *                 if (cnt >= 3) tot += cnt / 3;
 *                 i = j;
 *             }
 *             return Math.max(tot, 3 - m);
 *         } else {
 *             int tot = 0;
 *             int[] cnts = new int[3];
 *             for (int i = 0; i < n; ) {
 *                 int j = i;
 *                 while (j < n && cs[j] == cs[i]) j++;
 *                 int cnt = j - i;
 *                 if (cnt >= 3) {
 *                     tot += cnt / 3; cnts[cnt % 3]++;
 *                 }
 *                 i = j;
 *             }
 *             int base = n - 20, cur = base;
 *             for (int i = 0; i < 3; i++) {
 *                 if (i == 2) cnts[i] = tot;
 *                 if (cnts[i] != 0 && cur != 0) {
 *                     int t = Math.min(cnts[i] * (i + 1), cur);
 *                     cur -= t; tot -= t / (i + 1);
 *                 }
 *             }
 *             return base + Math.max(tot, 3 - m);
 *         }
 *     }
 * }
 *
 */
